package com.gwcloud.leetcode.tags.tree;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/** 
* @ClassName   : Leetcode099 
* @author      : ganwei 
* @date        : 2020年5月5日 
* @Description : 99. 恢复二叉搜索树 
*/
public class Leetcode0099 {
	private TreeNode x=null,y=null,pre=null;
	/**
	 * -解题思路，二叉搜索树中序遍历
	 */
    public void recoverTree(TreeNode root) {
    	inorder(root);
    	int tmp = x.val;
    	x.val = y.val;
    	y.val = tmp;
    }
    public void inorder(TreeNode root) {
        if(root == null) {
        	return;
        }
        inorder(root.left);
        if(x==null && pre.val > root.val) {
        	x = pre;
        }
        if(x!=null && pre.val > root.val) {
        	y = root;
        }
        pre = root;
        
        inorder(root.right);
    }
    public static void main(String[] args) {
    	
    }
}
